home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 09 - 1993 / 09.10 Oct 93 / Programmers' Challenge / replace.c
Encoding:
C/C++ Source or Header  |  1994-11-06  |  7.6 KB  |  272 lines  |  [TEXT/KAHL]
  1. /* Tom Elwertowski
  2.  *
  3.  * ReplaceAll( sourceHndl, replaceHndl, targetHndl )
  4.  *
  5.  * Replace all occurrances of sourceHndl in targetHndl with
  6.  * replaceHndl. If replace length is not greater than source
  7.  * length, replacement can be done as search proceeds.
  8.  * Otherwise, all occurrances must be found first in order
  9.  * to determine how much target will grow. A recursive
  10.  * solution is used in the latter case; matches are found
  11.  * on the way in and replacement occurs on the way out.
  12.  *
  13.  * Depending upon run length, substrings are moved either
  14.  * by a byte copy loop or by the BlockMove routine. A word
  15.  * move loop was considered and rejected. Best performance
  16.  * was achieved for these string sizes: byte loop: <9,
  17.  * word loop: 9-200 and BlockMove: >200. A word loop must
  18.  * check for and deal with word nonaligmnent however which
  19.  * resulted in more than a few lines of code and an inline
  20.  * solution appeared excessively cumbersome. When all three
  21.  * approaches were put in a subroutine, the additional
  22.  * overhead swamped the gain in most cases. The compromise
  23.  * was to use inline code with a byte loop for substrings
  24.  * up to 21 characters and a BlockMove otherwise.
  25.  */
  26.  
  27. #define kBlockMoveMin 22
  28.  
  29. typedef struct replaceParamBlock {
  30.     Handle    sourceHndl;
  31.     long    sourceSize;
  32.     char    *sourceStart;
  33.     char    *sourceEnd;
  34.     Handle    replaceHndl;
  35.     long    replaceSize;
  36.     char    *replaceStart;
  37.     char    *replaceEnd;
  38.     Handle    targetHndl;
  39.     long    targetSize;
  40.     char    *targetStart;
  41.     char    *targetEnd;
  42.     long    deltaSize;
  43. } replaceParamBlock, *replaceParamBlockPtr;
  44.  
  45. long replaceOne( char *target, long depth, long deltaOffset,
  46.     replaceParamBlockPtr replacePBPtr);
  47.  
  48. long ReplaceAll( Handle sourceHndl, Handle replaceHndl,
  49.     Handle targetHndl )
  50. {
  51.     replaceParamBlock replacePB;
  52.     char *target, *targetMatch, *targetOld, *targetNew,
  53.         *source, *replace;
  54.     long numReplace, deltaOffset, size;
  55.  
  56.     replacePB.sourceHndl = sourceHndl;
  57.     replacePB.sourceSize = GetHandleSize( sourceHndl);
  58.     replacePB.sourceStart = *sourceHndl;
  59.     replacePB.sourceEnd =
  60.         replacePB.sourceStart + replacePB.sourceSize;
  61.     replacePB.replaceHndl = replaceHndl;
  62.     replacePB.replaceSize = GetHandleSize( replaceHndl);
  63.     replacePB.replaceStart = *replaceHndl;
  64.     replacePB.replaceEnd =
  65.         replacePB.replaceStart + replacePB.replaceSize;
  66.     replacePB.targetHndl = targetHndl;
  67.     replacePB.targetSize = GetHandleSize( targetHndl);
  68.     replacePB.targetStart = *targetHndl;
  69.     replacePB.targetEnd = 
  70.         replacePB.targetStart + replacePB.targetSize;
  71.     replacePB.deltaSize =
  72.         replacePB.replaceSize - replacePB.sourceSize;
  73.  
  74.     numReplace = 0;
  75.     deltaOffset = 0;
  76.     if ( replacePB.deltaSize <= 0 ) {
  77.  
  78.         /* Iterative solution when 
  79.          * replacement not longer then source */
  80.         target = replacePB.targetStart;
  81.         while ( target < replacePB.targetEnd) {
  82.             if ( *target++ == *replacePB.sourceStart ) {
  83.  
  84.                 /* Beginning of potential match */
  85.                 targetMatch = target - 1;
  86.                 source = replacePB.sourceStart + 1;
  87.                 while ( source < replacePB.sourceEnd )
  88.                     if ( *target++ != *source++ )
  89.                         goto noMatch;
  90.  
  91.                 /* Match encountered */
  92.  
  93.                 /* Shift unchanged segment of  target */
  94.                 if (numReplace > 0 &&
  95.                         replacePB.deltaSize < 0 ) {
  96.                     targetOld = replacePB.targetStart;
  97.                     targetNew = replacePB.targetStart +
  98.                         deltaOffset;
  99.                     size = targetMatch -
  100.                         replacePB.targetStart;
  101.                     if ( size < kBlockMoveMin )
  102.                         while ( targetOld < targetMatch )
  103.                             *targetNew++ = *targetOld++;
  104.                     else
  105.                         BlockMove( targetOld, targetNew,
  106.                             size );
  107.                 }
  108.  
  109.                 /* Do replacement */
  110.                 replace = replacePB.replaceStart;
  111.                 targetNew = targetMatch + deltaOffset;
  112.                 if ( replacePB.replaceSize < kBlockMoveMin )
  113.                     while ( replace < replacePB.replaceEnd )
  114.                         *targetNew++ = *replace++;
  115.                 else
  116.                     BlockMove( replace, targetNew,
  117.                         replacePB.replaceSize );
  118.  
  119.                 numReplace++;
  120.                 deltaOffset += replacePB.deltaSize;
  121.                 replacePB.targetStart = target;
  122.             }
  123.  
  124.         noMatch:;
  125.         }
  126.  
  127.         /* End of target encountered */
  128.  
  129.         /* If replacements have occurred and
  130.          * replacement is shorter */
  131.         if ( numReplace > 0 && replacePB.deltaSize < 0 ) {
  132.  
  133.             /* Compress target from last match to end */
  134.             targetNew = replacePB.targetStart + deltaOffset;
  135.             targetOld = replacePB.targetStart;
  136.             size = replacePB.targetEnd -
  137.                 replacePB.targetStart;
  138.             if ( size < kBlockMoveMin )
  139.                 while ( targetOld < replacePB.targetEnd )
  140.                     *targetNew++ = *targetOld++;
  141.             else
  142.                 BlockMove( targetOld, targetNew, size );
  143.  
  144.             /* Resize target*/
  145.             SetHandleSize ( targetHndl,
  146.                 replacePB.targetSize += deltaOffset );
  147.             if ( MemError() != noErr)
  148.                 numReplace = -1;
  149.         }
  150.     }
  151.     else
  152.         /* Recursive solution when
  153.          * replacement is longer than source */
  154.         numReplace = replaceOne( replacePB.targetStart,
  155.             0, 0, &replacePB );
  156.  
  157.     return ( numReplace );
  158. }
  159.  
  160. long replaceOne( char *targetEntry, long depth,
  161.     long deltaOffset, replaceParamBlockPtr replacePBPtr )
  162. {
  163.     char *source, *replace, *target;
  164.     char *targetOld, *targetNew, *targetMatch;
  165.     long targetEntryOffset, targetMatchOffset, size;
  166.     long numReplace;
  167.     
  168.     target = targetEntry;
  169.     targetEntryOffset = targetEntry -
  170.         replacePBPtr->targetStart;
  171.     while ( target < replacePBPtr->targetEnd ) {
  172.         if ( *target++ == *replacePBPtr->sourceStart ) {
  173.  
  174.             /* Beginning of potential match */
  175.             targetMatch = target - 1;
  176.             targetMatchOffset = targetMatch -
  177.                 replacePBPtr->targetStart;
  178.             source = replacePBPtr->sourceStart + 1;
  179.             while ( source < replacePBPtr->sourceEnd )
  180.                 if ( *target++ != *source++ )
  181.                     goto noMatch;
  182.  
  183.             /* Match encountered. Look for next match */
  184.             numReplace = replaceOne( target, depth + 1,
  185.                 deltaOffset + replacePBPtr->deltaSize,
  186.                 replacePBPtr );
  187.  
  188.             /* Expand target after all matches found */
  189.             if ( numReplace > 0 ) {
  190.  
  191.                 /* Do replacement */
  192.                 targetMatch = replacePBPtr->targetStart +
  193.                     targetMatchOffset;
  194.                 targetNew = targetMatch + deltaOffset;
  195.                 if ( replacePBPtr->replaceSize <
  196.                         kBlockMoveMin ) {
  197.                     targetNew += replacePBPtr->replaceSize;
  198.                     replace = replacePBPtr->replaceEnd;
  199.                     while ( replace >
  200.                             replacePBPtr->replaceStart )
  201.                         *--targetNew = *--replace;
  202.                 }
  203.                 else
  204.                     BlockMove( replacePBPtr->replaceStart,
  205.                         targetNew,
  206.                         replacePBPtr->replaceSize );
  207.  
  208.                 /* Shift unchanged segment of target */
  209.                 if ( depth > 0 ) {
  210.                     targetOld = targetMatch;
  211.                     targetEntry =
  212.                         replacePBPtr->targetStart +
  213.                         targetEntryOffset;
  214.                     size = targetMatch - targetEntry;
  215.                     if ( size < kBlockMoveMin )
  216.                         while ( targetOld > targetEntry )
  217.                             *--targetNew = *--targetOld;
  218.                     else {
  219.                         targetNew -= size;
  220.                         BlockMove( targetEntry, targetNew,
  221.                             size );
  222.                     }
  223.                 }
  224.             }
  225.             return ( numReplace );
  226.         }
  227.         noMatch:;
  228.     }
  229.  
  230.     /* End of target encountered */
  231.     if ( depth > 0 ) {
  232.  
  233.         /* Resize target */
  234.         SetHandleSize ( replacePBPtr->targetHndl,
  235.             replacePBPtr->targetSize += deltaOffset );
  236.         if ( MemError() == noErr) {
  237.         
  238.             /* Update pointers after possible relocation */
  239.             replacePBPtr->targetStart =
  240.                 *replacePBPtr->targetHndl;
  241.             replacePBPtr->targetEnd =
  242.                 replacePBPtr->targetStart +
  243.                 replacePBPtr->targetSize;
  244.             replacePBPtr->replaceStart =
  245.                 *replacePBPtr->replaceHndl;
  246.             replacePBPtr->replaceEnd =
  247.                 replacePBPtr->replaceStart +
  248.                 replacePBPtr->replaceSize;
  249.  
  250.             /* Expand target from last match to end */
  251.             targetOld = replacePBPtr->targetEnd -
  252.                 deltaOffset;
  253.             targetEntry = replacePBPtr->targetStart +
  254.                 targetEntryOffset;
  255.             size = targetOld - targetEntry;
  256.             if ( size < kBlockMoveMin ) {
  257.                 targetNew = replacePBPtr->targetEnd;
  258.                 while ( targetOld > targetEntry )
  259.                     *--targetNew = *--targetOld;
  260.             }
  261.             else {
  262.                 targetNew = targetEntry + deltaOffset;
  263.                 BlockMove( targetEntry, targetNew, size );
  264.             }
  265.         }
  266.         else
  267.             depth = -1;
  268.     }
  269.  
  270.     return ( depth );
  271. }
  272.